/*
 输入正整数n(2<=n<=100)，把阶乘n!=1*2*3*…*n分解成素因子相乘的形式，从小到大输出各个素数（2、3、5、…）的指数。
 例如825=3*5^2*11应表示成(0,1,2,0,1)，表示分别有0、1、2、0、1个2、3、5、7、11。你的程序应忽略比最大素因子更大的素数。
 样例输入：
 5
 53
 样例输出：
 5!=3 1 1
 53!=49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1
 */
package com.yuan.algorithms.Algorithm_1;

import java.util.Scanner;

public class 素数因子和阶乘 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, count = 0;
        boolean judge = true;
        int[] prime = new int[100];
        //创建100以内的素数表
        for (int i = 2; i <= 100; i++) {
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    judge = false;
                    break;
                }
            }
            if (judge) {
                prime[count++] = i;
            } else {
                judge = true;
            }
        }
        while (sc.hasNext()) {
            n = sc.nextInt();
            int maxp = 0;
            int[] p = new int[100];
            for (int i = 2; i <= n; i++) {
                int m = i;
                for (int j = 0; j < count; j++) {
                    while (m % prime[j] == 0) {
                        m /= prime[j];
                        p[j]++;
                        if (j > maxp) {
                            maxp = j;
                        }
                    }
                }
            }
            System.out.print(n + "!=");
            for (int i = 0; i <= maxp; i++) {
                if (i == maxp) {
                    System.out.println(p[i]);
                } else {
                    System.out.print(p[i] + " ");
                }
            }
        }
    }

}
